package com.practice.niuke.new_direct_practice.class16;

import java.util.HashSet;

/**
 * 给定一个非空的字符串s，一个包含单词的数组arr，返回s可以被arr中的单词拼装组成
 * 的方案数，单词可以重复使用。
 * 例子：
 * s = "aaaab", arr = ["a", "aa", "ab"]
 * 方案一：s = a+a+a+ab
 * 方案二：s = a+aa+ab
 * 方案三：s = aa+a+ab
 * 返回3
 */
public class Code02_WorldBreak {
    /*
     *
     * 假设所有字符都是小写字母. 大字符串是str. arr是去重的单词表,
     * 每个单词都不是空字符串且可以使用任意次.
     *
     * 使用arr中的单词有多少种拼接str的方式. 返回方法数.
     *
     */

    /**
     * 暴力递归方法(O(n^3))，（从左往右不断尝试的模型）:
     * srt[index...]完全被words拼接成的话，返回有多少种方法数，主函数调用f(str, 0, words)
     *
     * @param str   目标字符串，固定参数
     * @param index 来到目标字符串的哪一个位置
     * @param words 单词表Set，arr -> words，固定参数
     * @return 方法数
     */
    public static int f(String str, int index, HashSet<String> words) {
        if (index == str.length()) {
            // base case
            // index来到了目标字符串的结尾字符的下一个位置，只有一种方法，那就是一个单词也不用
            return 1;
        }
        int ways = 0;
        // 枚举从index出发，所有可能成为第一个部分的情况
        // str[index...e]为第一部分
        for (int e = index; e < str.length(); e++) {
            // 如果words中有一个单词与str[index...e]相同，
            // 说明str[index...e]可以成为第一部分，此时后续的方法数为 f(str, e+1, words)
            if (words.contains(str.substring(index, e + 1))) {
                ways += f(str, e + 1, words);
            }
        }
        return ways;
    }

    /**
     * 暴力递归方法的动态规划改进(O(n^3))
     *
     * @param str 目标字符串
     * @param arr 单词数组
     * @return 方法数
     */
    public static int dp(String str, String[] arr) {
        if (str == null || arr == null) {
            // 无效参数过滤
            return -1;
        }
        HashSet<String> words = new HashSet<>();
        for (String word : arr) {
            words.add(word);
        }
        int N = str.length();
        int[] dp = new int[N + 1];//dp[0...N]
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            // str[i...]被words有几种方法搞定
            // str[i...j]能否作为第一个部分
            for (int j = i; j < N; j++) {
                if (words.contains(str.substring(i, j + 1))) {
                    dp[i] += dp[j + 1];
                }
            }
        }
        return dp[0];
    }

    public static int ways1(String str, String[] arr) {
        if (str == null || str.length() == 0 || arr == null || arr.length == 0) {
            return 0;
        }
        HashSet<String> map = new HashSet<>();
        for (String s : arr) {
            map.add(s);
        }
        return f(str, map, 0);
    }

    public static int f(String str, HashSet<String> map, int index) {
        if (index == str.length()) {
            return 1;
        }
        int ways = 0;
        for (int end = index; end < str.length(); end++) {
            if (map.contains(str.substring(index, end + 1))) {
                ways += f(str, map, end + 1);
            }
        }
        return ways;
    }

    public static int ways2(String str, String[] arr) {
        if (str == null || str.length() == 0 || arr == null || arr.length == 0) {
            return 0;
        }
        HashSet<String> map = new HashSet<>();
        for (String s : arr) {
            map.add(s);
        }
        int N = str.length();
        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            for (int end = i; end < N; end++) {
                if (map.contains(str.substring(i, end + 1))) {
                    dp[i] += dp[end + 1];
                }
            }
        }
        return dp[0];
    }

    /**
     * 前缀树节点
     */
    public static class Node {
        // 当前节点是否为某个字符串的结尾
        public boolean end;
        public Node[] nexts;

        public Node() {
            end = false;
            nexts = new Node[26];
        }
    }

    /**
     * 使用前缀树优化“判断一个前缀是否为单词表中的一个单词”过程后的主函数（O(建树代价)+O(n^2)）
     *
     * @param str 目标船
     * @param arr 单词表
     * @return int
     */
    public static int ways3(String str, String[] arr) {
        if (str == null || str.length() == 0 || arr == null || arr.length == 0) {
            return 0;
        }
        // 将arr单词表中的每一个单词，一个一个字符的挂在前缀树上，每个单词的结尾字符的前缀树节点都“描黑”（end为true）
        Node root = new Node();
        for (String s : arr) {
            char[] chs = s.toCharArray();
            Node node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new Node();
                }
                node = node.nexts[index];
            }
            node.end = true;
        }
        return g(str.toCharArray(), root, 0);
    }

    /**
     * 使用前缀树优化“判断一个前缀是否为单词表中的一个单词”过程后的递归函数
     *
     * @param str   目标字符串
     * @param root  前缀树的根节点
     * @param index 来到了str的哪个位置
     * @return int
     */
    public static int g(char[] str, Node root, int index) {
        if (index == str.length) {
            return 1;
        }
        int ways = 0;
        Node cur = root;
        for (int end = index; end < str.length; end++) {
            int path = str[end] - 'a';
            if (cur.nexts[path] == null) {
                break;
            }
            cur = cur.nexts[path];
            if (cur.end) {
                ways += g(str, root, end + 1);
            }
        }
        return ways;
    }

    /**
     * 使用前缀树优化“判断一个前缀是否为单词表中的一个单词”过程后的dp版本（O(建树代价)+O(n^2)）
     *
     * @param s   目标串
     * @param arr 单词表
     * @return 方法数
     */
    public static int ways4(String s, String[] arr) {
        if (s == null || s.length() == 0 || arr == null || arr.length == 0) {
            return 0;
        }
        // 将arr单词表中的每一个单词，一个一个字符的挂在前缀树上，每个单词的结尾字符的前缀树节点都“描黑”（end为true）
        Node root = new Node();
        for (String str : arr) {
            char[] chs = str.toCharArray();
            Node node = root;
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                index = chs[i] - 'a';
                if (node.nexts[index] == null) {
                    node.nexts[index] = new Node();
                }
                node = node.nexts[index];
            }
            node.end = true;
        }

        char[] str = s.toCharArray();
        int N = str.length;
        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            Node cur = root;
            // str[i...end]是不是单词表中的单词
            for (int end = i; end < N; end++) {
                int path = str[end] - 'a';
                if (cur.nexts[path] == null) {
                    break;
                }
                cur = cur.nexts[path];
                if (cur.end) {
                    // str[i...end]是单词表中的单词
                    dp[i] += dp[end + 1];
                }
            }
        }
        return dp[0];
    }

    // 以下的逻辑都是为了测试
    public static class RandomSample {
        public String str;
        public String[] arr;

        public RandomSample(String s, String[] a) {
            str = s;
            arr = a;
        }
    }

    // 随机样本产生器
    public static RandomSample generateRandomSample(char[] candidates, int num, int len, int joint) {
        String[] seeds = randomSeeds(candidates, num, len);
        HashSet<String> set = new HashSet<>();
        for (String str : seeds) {
            set.add(str);
        }
        String[] arr = new String[set.size()];
        int index = 0;
        for (String str : set) {
            arr[index++] = str;
        }
        StringBuilder all = new StringBuilder();
        for (int i = 0; i < joint; i++) {
            all.append(arr[(int) (Math.random() * arr.length)]);
        }
        return new RandomSample(all.toString(), arr);
    }

    public static String[] randomSeeds(char[] candidates, int num, int len) {
        String[] arr = new String[(int) (Math.random() * num) + 1];
        for (int i = 0; i < arr.length; i++) {
            char[] str = new char[(int) (Math.random() * len) + 1];
            for (int j = 0; j < str.length; j++) {
                str[j] = candidates[(int) (Math.random() * candidates.length)];
            }
            arr[i] = String.valueOf(str);
        }
        return arr;
    }

    public static void main(String[] args) {
        char[] candidates = {'a', 'b'};
        int num = 20;
        int len = 4;
        int joint = 5;
        int testTimes = 30000;
        boolean testResult = true;
        for (int i = 0; i < testTimes; i++) {
            RandomSample sample = generateRandomSample(candidates, num, len, joint);
            int ans1 = ways1(sample.str, sample.arr);
            int ans2 = ways2(sample.str, sample.arr);
            int ans3 = ways3(sample.str, sample.arr);
            int ans4 = ways4(sample.str, sample.arr);
            if (ans1 != ans2 || ans3 != ans4 || ans2 != ans4) {
                testResult = false;
            }
        }
        System.out.println(testTimes + "次随机测试是否通过：" + testResult);
    }

}
